/*********************************************************************************
    This software is created under the term GNU General Public License.
    You should have received a copy of the GNU General Public License.
    If not, write to the Free Software Foundation, 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.

list_cir:
    a implement of list, using data structure circular list. it is not a
    part of interface, but a part of implement of interface list. you
    can use it through interface list.

author: xiangyun.kong(lo-sor@hotmail.com)
create: 2-26-2011

changes:

**********************************************************************************/
#include <stdlib.h>

#include <assert.h>
#include <mem.h>
#include "list_cir.h"

ltc_iterator _ltc_new_node(ltc_iterator _pre, ltc_iterator _next, void *_val );
ltc_iterator _ltc_pos( list_cir *_lt, int _pos );

list_cir* ltc_create()
{
    list_cir* _lt;

    _lt = (list_cir*) palloc( sizeof(list_cir) );
    assert( _lt != NULL );

    _lt->head = (list_cir_node*) palloc( sizeof(list_cir_node) );
    assert( _lt->head != NULL );

    _lt->head->val = NULL;
    _lt->head->next = _lt->head;
    _lt->head->pre = _lt->head;
    _lt->tail = _lt->head;
    _lt->size = 0;

    return _lt;
}

void ltc_destroy( list_cir* _lt )
{
    list_cir_node* p, *pn;
    assert( _lt != NULL );
    assert( _lt->head != NULL );

    p = _lt->head->next;
    // off the circular
    _lt->head->next = NULL;
    while( p )
    {
        pn = p->next;
        pfree( p );
        p = pn;
    }
    pfree( _lt );
}

void ltc_pushb( list_cir* _lt, void* _val )
{
    if( _lt->tail->next == _lt->head )
    {
        _ltc_new_node( _lt->tail, _lt->tail->next, NULL );
    }
    _lt->tail->val = _val;
    _lt->tail = _lt->tail->next;
    ++_lt->size;
}

void ltc_pushf( list_cir *_lt, void *_val )
{
    if( _lt->head->pre == _lt->tail )
    {
        _ltc_new_node( _lt->head->pre, _lt->head, NULL );
    }
    _lt->head->pre->val = _val;
    _lt->head = _lt->head->pre;
    ++_lt->size;
}

ltc_iterator ltc_insert( list_cir *_lt, ltc_iterator _it, void *_val )
{
    ltc_iterator _pn;
    _pn = _ltc_new_node( _it, _it->next, _val );

    if( _it == _lt->tail )
        _lt->tail = _pn;
    return _pn;
}

ltc_iterator ltc_insertp( list_cir *_lt, int32 _pos, void *_val )
{
    if( _pos <= 0 )
    {
        ltc_pushf( _lt, _val );
        return _lt->head;
    }
    else if( _pos >= _lt->size )
    {
        ltc_pushb( _lt, _val );
        return _lt->tail->pre;
    }
    else
    {
        ltc_iterator _it = _ltc_pos( _lt, _pos );
        return ltc_insert( _lt, _it->pre, _val );
    }
}

void* ltc_get( list_cir *_lt, int32 _pos )
{
    if( _pos <= 0 )
        return ltc_front( _lt );
    else if( _pos >= ltc_size( _lt )-1 )
        return ltc_back( _lt );
    else
    {
        ltc_iterator _it = _ltc_pos( _lt, _pos );
        return ltc_val( _it );
    }
}

ltc_iterator ltc_find( list_cir *_lt, void *_key, compare _fun )
{
    ltc_iterator _it;
    for( _it = ltc_begin(_lt); _it != ltc_end(_lt); _it = ltc_next(_it) )
    {
        if( 0 == _fun( _key, ltc_val( _it ) ) )
            return _it;
    }
    return NULL;
}

void* ltc_front( list_cir *_lt )
{
    void* v = NULL;

    if( _lt->tail != _lt->head )
    {
        v = _lt->head->val;
    }

    return v;
}

void* ltc_back( list_cir *_lt )
{
    void* v = NULL;

    if( _lt->tail != _lt->head )
    {
        v = _lt->tail->pre->val;
    }

    return v;
}

int32 ltc_size( list_cir* _lt )
{
    return _lt->size;
}

ltc_iterator ltc_begin( list_cir *_lt )
{
    return _lt->head;
}

ltc_iterator ltc_end( list_cir *_lt )
{
    return _lt->tail;
}

ltc_iterator ltc_next( ltc_iterator _it )
{
    return _it->next;
}

ltc_iterator ltc_pre( ltc_iterator _it )
{
    return _it->pre;
}

void* ltc_popf( list_cir *_lt )
{
    void* v = NULL;

    if( _lt->tail != _lt->head )
    {
        v = _lt->head->val;
        _lt->head = _lt->head->next;
        --_lt->size;
    }

    return v;
}

void* ltc_popb( list_cir *_lt )
{
    void* v = NULL;

    if( _lt->tail != _lt->head )
    {
        v = _lt->tail->pre->val;
        _lt->tail = _lt->tail->pre;
        --_lt->size;
    }

    return v;
}

void* ltc_remove( list_cir *_lt, ltc_iterator _it )
{
    if( _it == _lt->head )
        return ltc_popf( _lt );
    else if( _it == _lt->tail->pre )
        return ltc_popb( _lt );
    else
    {
        void *_val = _it->val;
        _it->next->pre = _it->pre;
        _it->pre->next = _it->next;
        pfree( _it );
        return _val;
    }
}

void* ltc_removep( list_cir *_lt, int32 _pos )
{
    if( _pos <= 0 )
        return ltc_popf( _lt );
    else if( _pos >= ltc_size( _lt )-1 )
        return ltc_popb( _lt );
    else
    {
        ltc_iterator _it = _ltc_pos( _lt, _pos );
        return ltc_remove( _lt, _it );
    }
}

ltc_iterator _ltc_new_node( ltc_iterator _pre, ltc_iterator _next, void *_val )
{
    ltc_iterator _it;
    _it = (ltc_iterator)palloc( sizeof(list_cir_node) );
    assert( _it != NULL );

    _it->next = _next;
    _it->pre = _pre;
    _it->val = _val;
    _pre->next = _it;
    _next->pre = _it;

    return _it;
}

ltc_iterator _ltc_pos( list_cir *_lt, int _pos )
{
    ltc_iterator _it = ltc_begin( _lt );
    while( _pos-- > 0 )
        _it = ltc_next( _it );  
    return _it;
}

void* ltc_val( ltc_iterator _it )
{
    return _it->val;
}

void ltc_sort( list_cir *_lt, compare _fun )
{
    list_cir_node *sorted, *unsorted;

    if( _lt->size < 2 )
        return;

    sorted = _lt->head;
    unsorted = _lt->head->next;
    while( sorted != _lt->tail )
    {
        unsorted = sorted;
        while( unsorted != _lt->tail )
        {
            if( _fun(sorted->val, unsorted->val) > 0 )
            {
                (long)sorted->val ^= (long)unsorted->val;
                (long)unsorted->val ^= (long)sorted->val;
                (long)sorted->val ^= (long)unsorted->val;
            }
            unsorted = unsorted->next;
        }
        sorted = sorted->next;
    }
}
